<?php

/**
 * Created by PhpStorm.
 * User: Administrator
 * Date: 2017/9/29
 * Time: 15:47
 */

/**
 * Class node
 * @User: yfl
 * @Time: 2017年9月29日 15:50:39
 * @description:这篇文章主要介绍了PHP实现二叉树的深度优先与广度优先遍历方法,涉及php针对二叉树进行遍历的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下
 * @from:  http://www.jb51.net/article/72897.htm
 */
// 二叉树的广度有限遍历  使用一个队列实现
class Node
{
    public $data = null;
    public $left = null;
    public $right = null;
}

function breadth_first_traverse($btree)
{
    $traverse_data = array();
    $queue = array();
    array_unshift($queue, $btree);//跟节点入队
    while (!empty($queue)) { //持续输出节点 直到队列为空

        $cnode = array_pop($queue);//队尾元素出队

        $traverse_data[] = $cnode->data;
        //左节点先入队 ,然后右节点再入队
        if ($cnode->left != null) array_unshift($queue, $cnode->left);

        if ($cnode->right != null) array_unshift($queue, $cnode->right);
    }
    return $traverse_data;
}

function depth_first_traverse($btree)
{
    $traverse_data = array();
    $stack = array();
    array_push($stack, $btree);
    while (!empty($stack)) {
        $cnode = array_pop($stack);
        $traverse_data[] = $cnode->data;
        if ($cnode->right != null) array_push($stack, $cnode->right);
        if ($cnode->left != null) array_push($stack, $cnode->left);
    }
    return $traverse_data;
}

$root = new Node();
$node1 = new Node();
$node2 = new Node();
$node3 = new Node();
$node4 = new Node();
$node5 = new Node();
$node6 = new Node();
$root->data = 1;
$node1->data = 2;
$node2->data = 3;
$node3->data = 4;
$node4->data = 5;
$node5->data = 6;
$node6->data = 7;
$root->left = $node1;
$root->right = $node2;
$node1->left = $node3;
$node1->right = $node4;
$node2->left = $node5;
$node2->right = $node6;
$traverse = breadth_first_traverse($root);
print_r($traverse);
echo "";
$traverse = depth_first_traverse($root);
print_r($traverse);
